package org.example.sort;

public class MergeSort {
    
    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
        System.out.println("排序前:");
        for (int i = 0; i < arr.length; i++) {
            if (i != arr.length - 1) {
                System.out.print(arr[i] + ",");
            } else {
                System.out.print(arr[i]);
            }
        }
        System.out.println();
        // 归并排序
        mergeSort(arr, 0, arr.length - 1);
        System.out.println("排序后:");
        for (int i = 0; i < arr.length; i++) {
            if (i != arr.length - 1) {
                System.out.print(arr[i] + ",");
            } else {
                System.out.print(arr[i]);
            }
        }
        System.out.println();
    }
    /**
     * 归并排序主方法
     * @param arr 待排序数组
     * @param left 左边界
     * @param right 右边界
     */
    public static void mergeSort(int[] arr, int left, int right) {
        // 递归终止条件
        if (left < right) {
            // 找到中点
            int mid = (left + right) / 2;
            // 递归排序左半部分
            mergeSort(arr, left, mid);
            // 递归排序右半部分
            mergeSort(arr, mid + 1, right);
            // 合并两个有序部分
            // 创建临时数组存储合并结果
            int[] temp = new int[right - left + 1];
            // 左半部分指针
            int i = left;
            // 右半部分指针
            int j = mid + 1;
            // 临时数组指针
            int k = 0;
            // 比较两个子数组的元素，将较小的元素放入临时数组
            while (i <= mid && j <= right) {
                if (arr[i] <= arr[j]) {
                    temp[k++] = arr[i++];
                } else {
                    temp[k++] = arr[j++];
                }
            }
            // 将左半部分剩余元素复制到临时数组
            while (i <= mid) {
                temp[k++] = arr[i++];
            }
            // 将右半部分剩余元素复制到临时数组
            while (j <= right) {
                temp[k++] = arr[j++];
            }
            // 将临时数组的内容复制回原数组
            for (int idx = 0; idx < temp.length; idx++) {
                arr[left + idx] = temp[idx];
            }
        }
    }
}
